第5章 公開鍵暗号

鍵配送問題

平文を暗号化/復号するのには鍵が必要だが、その鍵を共有するのにも鍵が必要となること。

解決方法

事前共有

少数人数であれば簡単だが、対象の人が増えると鍵の数が膨大になる。

鍵配布センター

暗号化通信をするたびに鍵を鍵配布センターに作ってもらい、作ってもらった鍵を事前共有する。

鍵配布センターの社員への負荷が高い

能動的攻撃者に狙われやすい

Deffine-Hellman鍵交換

通信を行う二人がある情報をやりとり（これは盗聴されても問題ない）し、その情報を元にそれぞれ鍵を作って暗号化/復号を行う。

公開鍵暗号

暗号化と復号の鍵を別で持つため鍵を配送する必要がない。

公開鍵暗号

解決できない問題

公開鍵の認証

公開鍵が本当に正しいか判断できない。

対称暗号に比べて処理が遅い

RSA

アルゴリズム

暗号化

$ 暗号文 = 平文^E \bmod N

復号

$ 平文 = 暗号文^D \bmod N

1. Nを求める。大きな素数（例えば1024ビット）を用意して掛けたのがNになる。

$ N = p \times q

2. Lを求める。p -1とq - 1の最小公倍数になる。(Lはp - 1とq - 1の最小公倍数)

$ L = lcm(p - 1, q - 1)

3. Eを求める。EとLの最大公約数は1となる。

$ 1 < E < L

$ gcd(E, L) = 1

4. Dを求める。

$ 1 < D < L

$ E \times D \bmod L = 1

攻撃方法

ブルートフォース

極めて困難

EとNからDを求める

Nを素因数分解する

量子コンピューターなら解ける可能性がある

pとqを推測する

中間者攻撃

能動攻撃者が送信中のの公開鍵を奪って送信先に送らないようにし、能動攻撃者自身の公開鍵を元々の送信先に送る。

証明書で認証することで防ぐことができる。

ElGamal方式

Rabin方式

楕円曲線暗号